Introduction

• Some prime numbers have a surprisingly elegant shape.
• One of the most famous families is the Mersenne primes, numbers of the form $$2^p - 1$$ where $p$ itself is a prime number.
• These primes are deeply connected to perfect numbers—numbers whose factors add up to the number itself.
• This chapter explores what makes these primes special, how we find them, and why they continue to fascinate mathematicians.

Why Mathematicians Care About Special Primes

• Prime numbers are the “atoms” of arithmetic: every whole number factors into primes.
• Some primes have extra structure or patterns that make them easier to study.
• Special primes often lead to:
  • Faster algorithms
  • Surprising connections (like perfect numbers)
  • Deep insights into number theory
• Mersenne primes are among the most studied because:
  • They have a simple formula
  • They grow quickly
  • They are linked to ancient mathematical questions

Defining Mersenne Numbers and Mersenne Primes

• A Mersenne number is any number of the form $$M_p = 2^p - 1$$ where $p$ is a positive integer.
• A Mersenne prime is a Mersenne number that is also prime.
• Important notes:
  • $p$ must be prime for $2^p - 1$ to possibly be prime.
  • But even if $p$ is prime, $2^p - 1$ might not be prime.
• Examples:
  • $p = 2$: $2^2 - 1 = 3$ (prime)
  • $p = 3$: $2^3 - 1 = 7$ (prime)
  • $p = 11$: $2^{11} - 1 = 2047 = 23 \times 89$ (not prime)

Why the Expression \(2^p - 1\) Is So Important

• Numbers of the form $2^p - 1$ have special properties:
  • They are one less than a power of 2.
  • Their binary representation is just a string of $p$ ones:
    • Example: $2^5 - 1 = 31$ is $11111_2$.
• This simple structure makes them:
  • Easy to compute
  • Easy to test for primality (with special methods)
  • Useful in computer science and cryptography
• They also generate even perfect numbers through Euclid’s formula.

A Historical Glimpse: Marin Mersenne and His List

• Marin Mersenne (1588–1648) was a French monk and mathematician.
• He studied numbers of the form $2^p - 1$ and proposed a list of which $p$ values give primes.
• His list was partly correct and partly mistaken—understandable given the lack of modern tools.
• Mersenne’s work inspired centuries of research and gave these primes their name.

When Is \(2^p - 1\) Prime?

• A necessary condition: $p$ must be prime.
  • If $p$ is composite, say $p = ab$, then $$2^p - 1 = (2^a)^b - 1$$
  which is always composite.
• But $p$ being prime is not enough.
• Examples:
  • $p = 13$ → $2^{13} - 1 = 8191$ (prime)
  • $p = 17$ → $2^{17} - 1 = 131071$ (prime)
  • $p = 19$ → $2^{19} - 1 = 524287$ (prime)
  • $p = 23$ → $2^{23} - 1 = 8388607$ (not prime)
• So we need a special test.

The Lucas–Lehmer Test (Explained Gently)

The Lucas–Lehmer test is a fast and elegant way to check whether a number of the form $$M_p = 2^p - 1$$ is prime, but only when $p$ itself is prime.

The basic idea

1. Start with $$s_1 = 4$$
2. Repeatedly compute $$s_{n+1} = s_n^2 - 2$$ reducing the result modulo $M_p = 2^p - 1$ each time.
3. After doing this $p - 2$ times, look at the final value:
   • If it is 0, then $M_p$ is prime.
   • Otherwise, $M_p$ is composite.

This test is extremely efficient for large $p$, which is why computers use it to find giant primes.

Example: Testing whether \(2^5 - 1 = 31\) is prime

Here $p = 5$, so we will compute three values:
$s_1$, $s_2$, $s_3$ (because $p - 2 = 3$).

Step 1: Start the sequence

• $$s_1 = 4$$

Step 2: Compute \(s_2\)

• First compute $$s_2 = s_1^2 - 2 = 4^2 - 2 = 16 - 2 = 14$$
• Reduce modulo 31: $$14 \mod 31 = 14$$ (no change needed)

Step 3: Compute \(s_3\)

• Compute $$s_3 = s_2^2 - 2 = 14^2 - 2 = 196 - 2 = 194$$
• Reduce modulo 31:
  • Divide 194 by 31: $$31 \times 6 = 186$$
  • Subtract: $$194 - 186 = 8$$
  So $$s_3 \equiv 8 \pmod{31}$$

Step 4: Compute \(s_4\)

We need one more step because $p - 2 = 3$ means we compute up to $s_4$.

• Compute $$s_4 = s_3^2 - 2 = 8^2 - 2 = 64 - 2 = 62$$
• Reduce modulo 31: $$62 \mod 31 = 0$$

Final check

• The final value is 0
• Therefore, 31 is prime, and so $$2^5 - 1 = 31$$ is a Mersenne prime.

Additional Example: Showing that $2^{11} - 1$ Is Not Prime

We will test whether $$M_{11} = 2^{11} - 1 = 2047$$ is prime.

Since \(p = 11\), we must compute the Lucas–Lehmer sequence up to \(s_{10}\) (because \(p - 2 = 9\)).

Step 1: Start the sequence

• $$s_1 = 4$$

Step 2: Compute $s_2$

• $$s_2 = s_1^2 - 2 = 4^2 - 2 = 14$$
• Reduce modulo 2047: $$14 \mod 2047 = 14$$

Step 3: Compute $s_3$

• $$s_3 = 14^2 - 2 = 196 - 2 = 194$$
• Reduce modulo 2047: $$194 \mod 2047 = 194$$

Step 4: Compute $s_4$

• $$s_4 = 194^2 - 2 = 37636 - 2 = 37634$$
• Reduce modulo 2047:
  • Compute \(2047 \times 18 = 36846\)
  • Subtract: \(37634 - 36846 = 788\)
  So $$s_4 \equiv 788 \pmod{2047}$$

Step 5: Compute $s_5$

• $$s_5 = 788^2 - 2 = 620944 - 2 = 620942$$
• Reduce modulo 2047:
  • \(2047 \times 303 = 619,? \approx\)
    (We only need the remainder, not the exact multiple.)
  • The remainder is $$620942 \mod 2047 = 701$$
  So $$s_5 \equiv 701 \pmod{2047}$$

Step 6: Compute $s_6$

• $$s_6 = 701^2 - 2 = 491401 - 2 = 491399$$
• Reduce modulo 2047: $$491399 \mod 2047 = 119$$ So $$s_6 \equiv 119 \pmod{2047}$$

Step 7: Compute $s_7$

• $$s_7 = 119^2 - 2 = 14161 - 2 = 14159$$
• Reduce modulo 2047:
  • \(2047 \times 6 = 12282\)
  • Subtract: \(14159 - 12282 = 1877\)
  So $$s_7 \equiv 1877 \pmod{2047}$$

Step 8: Compute $s_8$

• $$s_8 = 1877^2 - 2 = 352,? - 2$$
  (Exact square not important — only the remainder matters.)
• Reduce modulo 2047: $$s_8 \equiv 240 \pmod{2047}$$

Step 9: Compute $s_9$

• $$s_9 = 240^2 - 2 = 57600 - 2 = 57598$$
• Reduce modulo 2047: $$57598 \mod 2047 = 282$$ So $$s_9 \equiv 282 \pmod{2047}$$

Step 10: Compute $s_{10}$

• $$s_{10} = 282^2 - 2 = 79524 - 2 = 79522$$
• Reduce modulo 2047: $$79522 \mod 2047 = 1736$$ So $$s_{10} \equiv 1736 \pmod{2047}$$

Final check

• The final value is not zero.
• Therefore, $$2^{11} - 1 = 2047$$ is not prime.

And indeed, $$2047 = 23 \times 89$$ so the Lucas–Lehmer test correctly identifies it as composite.

Examples of Known Mersenne Primes

Some early examples:

• $p = 2$: $3$
• $p = 3$: $7$
• $p = 5$: $31$
• $p = 7$: $127$
• $p = 13$: $8191$
• $p = 17$: $131071$
• $p = 19$: $524287$

Modern examples are enormous—millions of digits long.

How Rare Are They? Patterns, Myths, and Unknowns

• Mersenne primes are rare, but we don’t know how rare.
• There is no known formula that predicts which $p$ values will work.
• Myths and misconceptions:
  • Myth: They follow a simple pattern.
    • Reality: No pattern is known.
  • Myth: There are infinitely many.
    • Reality: This is unknown.
• What we do know:
  • They become less frequent as numbers grow.
  • But occasionally, a new one appears—often unexpectedly.

Modern Searches and the Role of Supercomputers

• Today, most Mersenne primes are found by distributed computing projects.
• Thousands of volunteers run software that tests candidate primes.
• Why computers love Mersenne primes:
  • The Lucas–Lehmer test is efficient.
  • Powers of 2 are easy to compute in binary.
• The largest known primes are almost always Mersenne primes.

Calculator

Exercises

1. Compute $2^p - 1$ for $p = 2, 3, 5$, and decide which are prime.

   Solution

   Compute $2^p - 1$ for $p = 2,3,5$ and decide which are prime.

   • For $p = 2$: $$2^2 - 1 = 4 - 1 = 3$$ 3 is prime.
   • For $p = 3$: $$2^3 - 1 = 8 - 1 = 7$$ 7 is prime.
   • For $p = 5$: $$2^5 - 1 = 32 - 1 = 31$$ 31 is prime.
   • Conclusion: All three, $3$, $7$, and $31$, are primes, so they are all Mersenne primes.
2. Explain why $p$ must be prime for $2^p - 1$ to be prime.

   Solution

   Explain why $p$ must be prime for $2^p - 1$ to be prime.

   • Key idea: If $p$ is not prime, say $p = ab$ with integers $a,b > 1$, then: $$2^p - 1 = 2^{ab} - 1$$
   • This can be factored using a standard algebraic pattern: $$2^{ab} - 1 = (2^a)^b - 1$$ which is divisible by $2^a - 1$.
   • So if $p$ is composite, $2^p - 1$ has a non-trivial factor and cannot be prime.
   • Therefore, for $2^p - 1$ to be prime, $p$ must be prime.
3. Check whether $2^{11} - 1$ is prime by factoring 2047.

   Solution

   Check whether $2^{11} - 1$ is prime by factoring 2047.

   • First compute: $$2^{11} - 1 = 2048 - 1 = 2047$$
   • Try small prime divisors:
     • Check division by $23$: $$2047 \div 23 = 89$$
     so $$2047 = 23 \times 89$$
   • Since 2047 has factors other than $1$ and itself, it is not prime.
   • So $2^{11} - 1$ is not a Mersenne prime.
4. Write the binary representation of $2^7 - 1$.

   Solution

   Write the binary representation of $2^7 - 1$.

   • First compute: $$2^7 - 1 = 128 - 1 = 127$$
   • In binary, $2^7$ is written as a 1 followed by seven 0s: $$2^7 = 10000000_2$$
   • Subtracting 1 gives a string of seven 1s: $$2^7 - 1 = 127 = 01111111_2$$
   • Often we drop the leading 0, so we can write: $$127 = 1111111_2$$
5. List three reasons why Mersenne primes are useful in computer science.

   Solution

   List three reasons why Mersenne primes are useful in computer science.

   Any three of the following (or similar) are acceptable:

   • Efficient arithmetic:
     • Numbers of the form $2^p - 1$ are convenient for computers because they are closely related to powers of 2, which fit naturally with binary hardware.
   • Fast primality testing:
     • The Lucas–Lehmer test works specifically and very efficiently for Mersenne numbers $2^p - 1$, making very large primes practical to find.
   • Use in cryptography / large prime generation:
     • Large Mersenne primes help test methods and hardware for generating big primes, which are important in cryptographic systems.
   • Simple binary structure:
     • A Mersenne number has a binary representation of all 1s, which can simplify certain bitwise operations.
6. For $p = 5$, run the first two steps of the Lucas–Lehmer sequence:
   • $s_1 = 4$
   • Compute $s_2 = s_1^2 - 2$

   Solution

   For $p = 5$, run the first two steps of the Lucas–Lehmer sequence: $s_1 = 4$, compute $s_2 = s_1^2 - 2$.

   • Given: $$s_1 = 4$$
   • Compute $s_2$: $$s_2 = s_1^2 - 2 = 4^2 - 2 = 16 - 2 = 14$$
   • For the full test, you would then reduce $s_2$ modulo $2^5 - 1 = 31$, but here:
     • $$14 \mod 31 = 14$$
   • Answer: $s_2 = 14$ (and modulo 31 it is still 14).
7. Research task: Find the current largest known Mersenne prime (just the exponent $p$).

   Solution

   Research task: Find the current largest known Mersenne prime (just the exponent $p$).

   • This value changes over time as new Mersenne primes are discovered.
   • The largest known Mersenne prime at the time of writing, is $2^{136279841} − 1$.
   • It was discovered by the Great Internet Mersenne Prime Search (GIMPS) in October 2024.
   • It has over 41 million digits (41,024,320 digits).
8. Explain why $2^{23} - 1$ is not prime.

   Solution

   Explain why $2^{23} - 1$ is not prime.

   • First compute: $$2^{23} - 1 = 8\,388\,608 - 1 = 8\,388\,607$$
   • We can show it is not prime by finding a factor. One such factorization is: $$8\,388\,607 = 47 \times 178\,481$$
   • Because it has non-trivial factors (47 and 178481), $2^{23} - 1$ is not prime.
   • Therefore, it is not a Mersenne prime.